#include "Stack.cpp"
#include "List.cpp"

bool IsSymmetric(LinkedList L)
{
    if (!L)
        return false;

    if (!L->next)
        return true;

    LNode *slow = L->next, *fast = L->next;
    LinkStack s;
    InitStack(s);
    int num = 1;
    while (fast && fast->next)
    {
        num++;
        Push(s, slow->data);
        slow = slow->next;
        fast = fast->next->next;
    }

    if (fast)
        slow = slow->next;
    
    while (slow)
    {
        int data;
        Pop(s, data);
        if (data != slow->data)
            return false;
        slow = slow->next;
    }

    return true;
}

int main(int argc, char const *argv[])
{
    LinkedList L;
    InitList(L);

    // 插入
    ListAppend(L, 2);
    ListAppend(L, 5);
    ListAppend(L, 9);
    ListAppend(L, 6);
    ListAppend(L, 9);
    ListAppend(L, 5);
    ListAppend(L, 2);
    PrintList(L);

    bool res = IsSymmetric(L);
    printf("%d \n", res);
    return 0;
}
